package PersonStu.sanqi;

import com.sun.media.sound.SoftTuning;

import java.io.PushbackInputStream;

/**
 * @Author by KoVaVo
 * @Date 2023-01-03 21:11
 * @Desc: 给定一个int类型数组，已知只有一个数出现了1次，其他的数都出现了k次，如何使用O(1)的额外空间找到这个数
 *
 * 思路：
 * 使用异或
 * 出现k次，就使用k进制找，将对应的k进制放到一个数组中。
 * 然后将这个k进制的数组在取模所得的一个数组转换成10进制的数，就是那个出现了1次的数字
 */
public class code_25_KTimesOneTime {
    public static int onceTime(int [] arr,int k){
        int [] e0 = new int[32];
        for (int i = 0; i != arr.length; i++) {
            setExlusivOr(e0,arr[i],k);
        }
        int res = getNumFromSysNum(e0,k);
        return res;
    }

    private static void setExlusivOr(int[] e0, int value, int k) {
        int [] curSysNum = getSysNumFromNum(value,k);
        for (int i = 0; i != e0.length; i++) {
            e0[i] = (e0[i] + curSysNum[i]) % k;
        }
    }

    //把e0组成的数字转换成k进制
    public static int[] getSysNumFromNum(int value,int k){
        int[] res = new int[32];
        int index = 0;
        while(value != 0) {
            res[index++] = value%k;
            value = value /k;
        }
        return res;
    }

    public static int getNumFromSysNum(int[] e0,int k){
        int res = 0;
        for(int i = e0.length-1;i != -1;i--){
            res = res * k + e0[i];
        }
        return res;
    }



    public static void main(String[] args) {
        int[] nums = {12,21,21,21,2,2,2,10,10,10};
        System.out.println(onceTime(nums,3));
    }













}
